package com.lql.algorithm;

/**
 * 非递归二分查找
 */
public class NonRecursiveBinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.err.println(nonRecursiveBinarySearch(arr, 1));
        System.err.println(recursiveBinarySearch(arr, 11, 0, arr.length - 1));
    }

    /**
     * 非递归实现二分查找
     *
     * @param arr    有序数组
     * @param target 待查找数据
     * @return 查找到的下标索引，未找到返回-1
     */
    public static int nonRecursiveBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target < arr[middle]) {
                //向左查找
                right = middle - 1;
            } else if (target == arr[middle]) {
                //找到
                return middle;
            } else {
                //向右查找
                left = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 递归实现二分查找
     *
     * @param arr    有序数组
     * @param target 目标值
     * @param left   左边开始索引
     * @param right  右边开始索引
     * @return 查找到的下标索引，未找到返回-1
     */
    public static int recursiveBinarySearch(int[] arr, int target, int left, int right) {
        int middle = (left + right) / 2;
        if (left <= right && arr[middle] > target) {
            //左递归
            return recursiveBinarySearch(arr, target, left, middle - 1);
        } else if (left <= right && arr[middle] < target) {
            //右递归
            return recursiveBinarySearch(arr, target, middle + 1, right);
        } else if (left <= right && arr[middle] == target) {
            return middle;
        }
        return -1;
    }
}
